
#include <assert.h>
#include <stdlib.h>
#include "PQ.h"

typedef struct PQnode* PQlink;
typedef struct pq* PQ;

#define test(C, B, A) 4*(C) + 2*(B) + 1*(A)

struct PQnode {
    Item key;
    PQlink l;
    PQlink r;
};

struct pq {
    PQlink *bq;
};

int maxBQsize;
PQ pq;

static PQlink z = NULL;

///////////////////////////////////辅助函数/////////////////////////////////
PQlink pair(PQlink p, PQlink q) {
    if (p->key < q->key) {
        p->r = q->l;
        q->l = p;
        return q;
    }else {
        q->r = p->l;
        p->l = q;
        return p;
    }
}

void BQjoin(PQlink *a, PQlink *b) {
    int i;
    PQlink c = z;
    for (i = 0; i < maxBQsize; i++) {
        switch (test(c != z, b[i] != z, a[i] != z)) {
            case 2:
                a[i] = b[i];
                break;
            case 3:
                c = pair(a[i], b[i]);
                a[i] = z;
                break;
            case 4:
                a[i] = c;
                c = z;
                break;
            case 5:
                c = pair(c, a[i]);
                a[i] = z;
                break;
            case 6:
            case 7:
                c = pair(c, b[i]);
                break;
            default:
                break;
        }
    }
}

// 计算无符号整数的二进制位数
int count_bits(unsigned int n) {
    if (n == 0) {
        return 0; // 或者 1，取决于你对“0的位数”的定义。如果定义为所需存储的最小位数，通常是1位。但如果指“有效位”，0就没有有效位。
                   // 很多上下文会将 0 视为 0 位有效位，或者特殊处理为 1 位。这里返回 0。
    }
    int count = 0;
    while (n > 0) {
        n >>= 1; // 右移一位
        count++; // 计数器加一
    }
    return count;
}

/////////////////////////////////接口操作////////////////////////////////////
void PQinit(int maxN) {
    pq = (PQ)malloc(sizeof(*pq));
    maxBQsize = count_bits(maxN);
    pq->bq = (PQlink *)malloc(maxBQsize * sizeof(PQlink));

    int i;
    for (i = 0; i < maxBQsize; i++) {
        pq->bq[i] = z;
    }
}

void PQinsert(Item v) {
    PQlink t = malloc(sizeof(*t));
    PQlink c = t;
    c->key = v;
    c->l = z;
    c->r = z;
    int i;

    for (i = 0; i < maxBQsize; i++) {
        if (c == z) {
            break;
        }
        if (pq->bq[i] == z) {
            pq->bq[i] = c;
            break;
        }
        c = pair(c, pq->bq[i]);
        pq->bq[i] = z;

    }
}

Item PQdelmax() {
    int i;
    int max;
    PQlink x;
    Item v;
    PQlink temp[maxBQsize];

    for (i = 0, max = -1; i < maxBQsize; i++) {
        if (pq->bq[i] != z) {
            if ((max == -1) || (v < pq->bq[i]->key)) {
                max = i;
                v = pq->bq[max]->key;
            }
        }
    }

    x = pq->bq[max]->l;
    for (i = max; i < maxBQsize; i++) {
        temp[i] = z;
    }
    for (i = max; i > 0; i--) {
        temp[i-1] = x;
        x = x->r;
        temp[i-1]->r = z;
    }

    free(pq->bq[max]);
    pq->bq[max] = z;

    BQjoin(pq->bq, temp);
    return v;
}